package demo1;

import java.util.LinkedList;
import java.util.Queue;

public class MyTree {

    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }
    TreeNode root;
    public TreeNode createBinaryTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        TreeNode I = new TreeNode('H');
        TreeNode J = new TreeNode('H');
        TreeNode K = new TreeNode('H');



        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = I;
        D.right = J;
        E.left = K;
       E.right = H;

        return A;
    }
    //获取树中节点的个数
   public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }
    //获取叶⼦节点的个数
   public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
       return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    // ⼦问题思路求叶⼦结点个数

    //获取第K层节点的个数
   public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }
    //获取⼆叉树的⾼度
   public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH,rightH) + 1;
    }
    //检测值为value的元素是否存在
   public TreeNode find(TreeNode root, int val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode findleft = find(root.left,val);
        TreeNode findright = find(root.right,val);
        if(findleft != null){
            return findleft;
        }else if (findright != null){
            return findright;
        }else {
            return null;
        }
    }

    //层序遍历
    void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.val + "");
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }

        }
    }

    //判断⼀棵树是不是完全⼆叉树
    boolean isCompleteTree(TreeNode root){
       if(root == null){
           return true;
       }
       Queue<TreeNode> queue = new LinkedList<>();
       TreeNode node = root;
       while(node != null){
           queue.offer(node.left);
           queue.offer(node.right);
           node = queue.poll();
       }
       while(!queue.isEmpty()){
           node = queue.poll();
           if(node != null){
               return false;
           }
       }
       return true;
    }
    //前序遍历
   public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
       System.out.print(root.val + " ");
       preOrder(root.left);
       preOrder(root.right);
   }
    //中序遍历
   public void inOrder(TreeNode root){
     if(root == null){
         return ;
     }
     inOrder(root.left);
       System.out.print(root.val + " ");
       inOrder(root.right);
   }
    //后序遍历
   public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
       System.out.print(root.val + " ");
   }
}
